﻿// 3403. 我想回家.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
* https://www.acwing.com/problem/content/3406/
某国正处于激烈的内战之中，该国的各个城市按照支持领导人的不同分属两个阵营。

作为一个商人，M先生并不关心政治，但他能够感受到目前事态的严峻。

你需要帮助他尽快回家。

出于安全的考虑，你所提供的回家线路中，最多只能包含一条连接两个不同阵营城市的道路。

请你计算，M先生回家所需花费的最短时间。

输入格式
输入包含多组测试数据。

每组数据第一行包含整数 N，表示该国家的城市数量。

第二行包含整数 M，表示该国家的道路数量。

接下来 M行，每行包含三个整数 A,B,T，表示城市 A 和城市 B之间存在一条道路，通过它的时间为 T。

最后一行包含 N 个整数 1或 2
，其中的第 i个整数是 1，则表示城市 i位于阵营 1
，否则，表示城市 i 位于阵营 2。

所有城市编号 1∼N。

为了简化问题，我们假设 M先生是从城市 1出发，目的地是城市 2
，并且城市 1一定位于阵营 1
，城市 2一定位于阵营 2。

注意，所有道路都是双向的，且两个城市之间最多只有一条道路。

输入 N=0时，表示输入结束。

输出格式
每组数据输出一行一个结果，表示最短时间。如果无法到达目的地，则输出 −1。

数据范围
每个输入最多包含 10组数据。
2≤N≤600
,
0≤M≤10000
,
1≤A,B≤N
,
1≤T≤500
输入样例：
2
1
1 2 100
1 2
3
3
1 2 100
1 3 40
2 3 50
1 2 1
5
5
3 1 200
5 3 150
2 5 160
4 3 170
4 2 170
1 2 2 2 1
0
输出样例：
100
90
540
*/
int main()
{
    std::cout << "Hello World!\n";
}

 